package com.chenken;

import java.util.LinkedList;
import java.util.Queue;

import com.chenken.printer.BinaryTreeInfo;

public abstract class BinaryTree<E>  implements BinaryTreeInfo{

	protected int size;
	
	protected Node<E> root;
	
	public void clear() {
		root = null;
		size = 0;
	}
	
	/**
	 * 找到前驱节点
	 * 中序遍历时的前一个节点
	 * @param node
	 * @return
	 */
	public Node<E> predecessor(Node<E> node){
		if(node == null) {
			return null;
		}
		Node<E> p = node.left;
		if(p != null) {
			while(node.right != null) {
				p = p.right;
			}
			return p;
		}
		while(node.parent !=null && node == node.parent.left) {
			node = node.parent;
		}
		return node.parent;
	}
	
	/**
	 * 找到后继节点
	 * 中序遍历时的后前一个节点
	 * @param node
	 * @return
	 */
	public Node<E> successor(Node<E> node){
		if(node == null) {
			return null;
		}
		Node<E> p = node.right;
		if(p != null) {
			while(p.left != null) {
				p = p.left;
			}
			return p;
		}
		while(node.parent !=null && node == node.parent.right) {
			node = node.parent;
		}
		return node.parent;
	}
	
	public int height() {
		if(root == null) {
			return 0;
		}
		/**
		 * 	树的高度
		 */
		int height = 0;
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);//将根节点入队
		/**
		 * 	存储每一层的元素数量,根节点入队,层数为1
		 */
		int levelSize = 1;
		while(!queue.isEmpty()) {
			Node<E> node = queue.poll();//将队头出队
			levelSize--;
			if(node.left!=null) {
				queue.offer(node.left);//将左子节点入队
			}
			if(node.right!=null) {
				queue.offer(node.right);//将右子节点入队
			}
			/**
			 *  根节点出队后，说明第一层访问完毕
			 */
			if(levelSize == 0) {	
				levelSize = queue.size();//将下一层的数量赋值给levelSize
				height++;//一层访问完毕，高度加一
			}
		}
		return height;
	}
	
	protected Node<E> createNewNode(E element,Node<E> parent){
		return new Node<E>(element, parent);
	}
	
	
	protected static class Node<E>{
		E element;
		Node<E> left;
		Node<E> right;
		Node<E> parent;
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		public boolean hasOneChild() {
			return (left != null && right == null) || (left == null && right != null);
		}
		
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
		
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
		public boolean isLeftChild() {
			return parent !=null && parent.left == this;
		}
		
		public boolean isRightChild() {
			return parent !=null && parent.right == this;
		}
		
		public Node<E> sibling(){
			if(isLeftChild()) {
				return parent.right;
			}
			if(isRightChild()) {
				return parent.left;
			}
			return null;
		}
	}
	
	
	@Override
	public Object root() {
		return root;
	}

	@Override
	public Object left(Object node) {
		return ((Node<E>)node).left;
	}

	@Override
	public Object right(Object node) {
		return ((Node<E>)node).right;
	}

	@Override
	public Object string(Object node) {
		return ((Node<E>)node);
	}

}
